Logic programming
Logic programming is a type of which is largely based on . Any program written in a logic is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include , (ASP) and . Prolog Prolog is a language associated with and . Prolog has its roots in , a , and unlike many other s, Prolog is intended primarily as a programming language: the program logic is expressed in terms of relations, represented as facts and . A computation is initiated by running a query over these relations. The language was first conceived by and his group in Marseille, France, in the early 1970s and the first Prolog system was developed in 1972 by Colmerauer with Philippe Roussel. Prolog was one of the first logic programming languages, and remains the most popular among such languages today, with several free and commercial implementations available. The language has been used for , s, , s, and , as well as its original intended field of use, . Modern Prolog environments support the creation of s, as well as administrative and networked applications. Prolog is well-suited for specific tasks that benefit from rule-based logical queries such as searching databases, systems, and filling templates. Data types Prolog's single is the term. Terms are either s, numbers, variables or compound terms. *An atom is a general-purpose name with no inherent meaning. Examples of atoms include x, red, 'Taco', and 'some atom'. *'Numbers' can be or s. ISO standard compatible Prolog systems can check the Prolog flag "bounded". Most of the major Prolog systems support arbitrary length integer numbers. *'Variables' are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms. *A compound term is composed of an atom called a "functor" and a number of "arguments", which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's . An atom can be regarded as a compound term with zero. An example of a compound term is person_friends(zelda,tom,jim). Special cases of compound terms: * A List is an ordered collection of terms. It is denoted by square brackets with the terms separated by commas or in the case of the empty list, []. For example, 1,2,3 or red,green,blue. * Strings: A sequence of characters surrounded by quotes is equivalent to either a list of (numeric) character codes, a list of characters (atoms of length 1), or an atom depending on the value of the Prolog flag double_quotes. For example, "to be, or not to be". provides the atom/1, number/1, integer/1, and float/1 predicates for . Rules and facts Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to . There are two types of clauses: facts and rules. A rule is of the form Head :- Body. and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's goals. The built-in ,/2 (meaning a 2-arity with name ,) denotes of goals, and ;/2 denotes . Conjunctions and disjunctions can only appear in the body, not in the head of a rule. Clauses with empty bodies are called facts. An example of a fact is: cat(tom). which is equivalent to the rule: cat(tom) :- true. The built-in predicate true/0 is always true. Given the above fact, one can ask: is tom a cat? ?- cat(tom). Yes what things are cats? ?- cat(X). X = tom Clauses with bodies are called rules. An example of a rule is: animal(X) :- cat(X). If we add that rule and ask what things are animals? ?- animal(X). X = tom Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list (length(List, L), given a list List) as well as to generate a list skeleton of a given length (length(X, 5)), and also to generate both list skeletons and their lengths together (length(X, L)). Similarly, append/3 can be used both to append two lists (append(ListA, ListB, X) given lists ListA and ListB) as well as to split a given list into parts (append(X, Y, List), given a list List). For this reason, a comparatively small set of library predicates suffices for many Prolog programs. As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like , using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate write/1 displays a term on the screen. Execution Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a refutation of the negated query. The resolution method used by Prolog is called . If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case, the system creates a choice-point, the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy is called chronological . For example: mother_child(trude, sally). father_child(tom, sally). father_child(tom, erica). father_child(mike, tom). sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). This results in the following query being evaluated as true: ?- sibling(sally, erica). Yes This is obtained as follows: Initially, the only matching clause-head for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z,sally), parent_child(Z,erica)). The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally). Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally). This goal can be proved using the fact father_child(tom, sally), so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica). Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like: ?- father_child(Father, Child). enumerates all valid answers on backtracking. Notice that with the code as stated above, the query ?- sibling(sally, sally). also succeeds. One would insert additional goals to describe the relevant restrictions, if desired. Modules For , Prolog provides a . The module system is standardised by ISO. However, not all Prolog compilers support modules, and there are compatibility problems between the module systems of the major Prolog compilers. Consequently, modules written on one Prolog compiler will not necessarily work on others. Reference Category:Programming